﻿#define _CRT_SECURE_NO_WARNINGS 1
//猜数字游戏的规则如下：
//
//每轮游戏，我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。
//如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。
//你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有 3 种可能的情况（ - 1，1 或 0）：
//
//- 1：我选出的数字比你猜的数字小 pick < num
//1：我选出的数字比你猜的数字大 pick > num
//0：我选出的数字和你猜的数字一样。恭喜！你猜对了！pick == num
//返回我选出的数字。
//
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/guess-number-higher-or-lower
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
///**
//* Forward declaration of guess API.
//* @param  num   your guess
//* @return 	     -1 if num is lower than the guess number
//*			      1 if num is higher than the guess number
//*               otherwise return 0
//* int guess(int num);
//*/
//
//int guessNumber(int n){
//	int l = 1;
//	int r = n;
//	while (l<r)
//	{
//		int m = l + (r - l) / 2;
//		if (guess(m) == 0)
//		{
//			return m;
//		}
//		else if (guess(m) == 1)
//		{
//			l = m + 1;
//		}
//		else
//		{
//			r = m - 1;
//		}
//	}
//	return l;
//}








//给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
//
//进阶：不要 使用任何内置的库函数，如  sqrt 。
//
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/valid-perfect-square
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//bool isPerfectSquare(int num){
//	int i = 1;
//	while (num>0)
//	{
//		num -= i;
//		i += 2;
//	}
//	return num == 0;
//}







//
//给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true ；否则，返回 false 。
//
//整数 n 是 4 的幂次方需满足：存在整数 x 使得 n == 4x
//
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/power-of-four
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//bool isPowerOfFour(int n){
//	while (n)
//	{
//		if (n % 4 == 0)
//		{
//			n /= 4;
//		}
//		else
//		{
//			break;
//		}
//	}
//	return n == 1;
//}







//给你一个整数 n ，请你判断 n 是否为 丑数 。如果是，返回 true ；否则，返回 false 。
//丑数 就是只包含质因数 2、3 和 / 或 5 的正整数。
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/ugly-number
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//bool isUgly(int n){
//	while (n)
//	{
//		if (n % 2 == 0)
//		{
//			n /= 2;
//		}
//		else if (n % 3 == 0)
//		{
//			n /= 3;
//		}
//		else if (n % 5 == 0)
//		{
//			n /= 5;
//		}
//		else
//		{
//			break;
//		}
//	}
//	return n == 1;
//}







//给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。
//int addDigits(int num){
//	int count = 0;
//	while (num>9)
//	{
//		int tmp = num;
//		count = 0;
//		while (tmp)
//		{
//			count += tmp % 10;
//			tmp /= 10;
//		}
//		num = count;
//	}
//	return num;
//}







//给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
//void moveZeroes(int* nums, int numsSize){
//	int i = 0;
//	int j = 0;
//	int count = 0;
//	for (i = 0; i<numsSize; i++)
//	{
//		if (nums[i] != 0)
//		{
//			nums[j++] = nums[i];
//		}
//		else
//		{
//			count++;
//		}
//	}
//	for (i = 1; i <= count; i++)
//	{
//		nums[numsSize - i] = 0;
//	}
//	return nums;
//}








//给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。
//整数 n 是 3 的幂次方需满足：存在整数 x 使得 n == 3x
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/power-of-three
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//bool isPowerOfThree(int n){
//	if (n == 0)
//	{
//		return 0;
//	}
//	while (n % 3 == 0)
//	{
//		n /= 3;
//	}
//	if (n == 1)
//	{
//		return 1;
//	}
//	else
//	{
//		return 0;
//	}
//}








//给定两个字符串 s 和 t，判断它们是否是同构的。
//
//如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。
//
//每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。
//
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/isomorphic-strings
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//bool isIsomorphic(char * s, char * t){
//	int s1[128] = { 0 };
//	int t1[128] = { 0 };
//	int i = 0;
//	int sc = 0;
//	int tc = 0;
//	for (i = 0; s[i] != '\0'; i++)
//	{
//		if (s1[s[i]] == 0)
//		{
//			s1[s[i]] = ++sc;
//		}
//		if (t1[t[i]] == 0)
//		{
//			t1[t[i]] = ++tc;
//		}
//		if (s1[s[i]] != t1[t[i]])
//		{
//			return 0;
//		}
//	}
//	return 1;
//}








//统计所有小于非负整数 n 的质数的数量。
//int countPrimes(int n){
//	unsigned char*a = (unsigned char*)calloc(n, sizeof(unsigned char));
//	int count = 0;
//	int sq = sqrt(n);
//	for (int i = 2; i <= sq; i++)
//	{
//		if (a[i] == 0)
//		{
//			for (int j = i*i; j<n; j += i)
//			{
//				a[j] = 1;
//			}
//		}
//	}
//	for (int i = 2; i<n; i++)
//	{
//		if (a[i] == 0)
//		{
//			count++;
//		}
//	}
//	return count;
//}








//编写一个算法来判断一个数 n 是不是快乐数。
//
//「快乐数」定义为：
//
//对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
//然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
//如果 可以变为  1，那么这个数就是快乐数。
//如果 n 是快乐数就返回 true ；不是，则返回 false 。
//
//
//
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/happy-number
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//int add(int x)
//{
//	int sum = 0;
//	while (x)
//	{
//		sum += (x % 10)*(x % 10);
//		x /= 10;
//	}
//	return sum;
//}
//bool isHappy(int n){
//	int s = n;
//	int q = n;
//	do
//	{
//		q = add(q);
//		q = add(q);
//		s = add(s);
//		if (s == 1 || q == 1)
//		{
//			return 1;
//		}
//	} while (s != q);
//	return 0;
//}